4.7 KB · ⇊ 3 parts · ⤓ Micron 4.7 KB · ⤓ HTML 25.6 KB

top

In relational database theory, an equality-generating dependency (EGD) is a certain kind of constraint on data. It is a subclass of the class of embedded dependencies (ED).

An algorithm known as the chase takes as input an instance that may or may not satisfy a set of EGDs (or, more generally, a set of EDs), and, if it terminates (which is a priori undecidable), output an instance that does satisfy the EGDs.

An important subclass of equality-generating dependencies are functional dependencies.

• Definition

• References

• Further reading

An equality-generating dependency is a sentence in first-order logic of the form:

∀ ∀ x 1 , … … , x n . ϕ ϕ ( x 1 , … … , x n ) → → ψ ψ ( y 1 , … … , y m ) {\displaystyle \forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \psi (y_{1},\ldots ,y_{m})}

where { y 1 , … … , y m } ⊆ ⊆ { x 1 , … … , x n } {\displaystyle \{y_{1},\ldots ,y_{m}\}\subseteq \{x_{1},\ldots ,x_{n}\}} , ϕ ϕ {\displaystyle \phi } is a conjunction of relational and equality atoms and ψ ψ {\displaystyle \psi } is a non-empty conjunction of equality atoms. A relational atom has the form R ( w 1 , … … , w h ) {\displaystyle R(w_{1},\ldots ,w_{h})} and an equality atom has the form w i = w j {\displaystyle w_{i}=w_{j}} , where each of the terms w , . . . , w h , w i , w j {\displaystyle w,...,w_{h},w_{i},w_{j}} are variables or constants.

Actually, one can remove all equality atoms from the body of the dependency without loss of generality.cite-ref-1[1] For instance, if the body consists in the conjunction A ( x , y ) ∧ ∧ B ( y , z , w ) ∧ ∧ y = 3 ∧ ∧ z = w {\displaystyle A(x,y)\land B(y,z,w)\land y=3\land z=w} , then it can be replaced with A ( x , 3 ) ∧ ∧ B ( 3 , z , z ) {\displaystyle A(x,3)\land B(3,z,z)} (analogously replacing possible occurrences of the variables y {\displaystyle y} and w {\displaystyle w} in the head).

An equivalent definition is the following:cite-ref-2[2]

∀ ∀ x 1 , … … , x n . ϕ ϕ ( x 1 , … … , x n ) → → x i = x j {\displaystyle \forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow x_{i}=x_{j}}

where i , j ∈ ∈ { 1 , … … , n } {\displaystyle i,j\in \{1,\ldots ,n\}} . Indeed, generating a conjunction of equalities is equivalent to have multiple dependencies which generate only one equality.

cite-note-11. ↑ (Abiteboul, Hull & Vianu 1995, p. 217)

cite-note-22. ↑ citerefcal-pieris2011Calì, Andrea; Pieris, Andreas (2011). On Equality-Generating Dependencies in Ontology Querying - Preliminary Report (PDF). Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2011).

• citerefabiteboulhullvianu1995Abiteboul, Serge; Hull, Richard B.; Vianu, Victor (1995). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0.

• Alin Deutsch, FOL Modeling of Integrity Constraints, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf